package com.jinan.algorithm.Backtrace;

import com.jinan.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的最小深度
 * 给定一个二叉树,找出其最小深度。
 * ★
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 */
public class TreeMinDeep {
    public static void main(String[] args) {
        TreeNode<Integer> node5 = new TreeNode<>(3,null,null);
        TreeNode<Integer> node4 = new TreeNode<>(9,null,null);
        TreeNode<Integer> node3 = new TreeNode<>(20,null,null);
        TreeNode<Integer> node2 = new TreeNode<>(15,node4,node5);
        TreeNode<Integer> node1 = new TreeNode<>(7,node2,node3);
        System.out.println(minDeepDFS(node1));
        System.out.println(minDeepBFS(node1));
    }

    /**
     * 递归
     * 递归方法检查左右子树的最小深度，取其中较小者加1（根节点的贡献）作为当前节点的最小深度。
     * 如果左右子树之一为空，则取另一侧的深度，因为我们要找的是最短路径。
     * @param treeNode
     * @return
     */
    public static int minDeepDFS(TreeNode<Integer> treeNode){
        if(treeNode == null) return 0;
        if (treeNode.left == null && treeNode.right == null){
            return 1;
        }
        int min= Integer.MAX_VALUE;
        if(treeNode.left != null){
            min=Math.min(min,minDeepDFS(treeNode.left));
        }
        if (treeNode.right != null){
            min=Math.min(min,minDeepDFS(treeNode.right));
        }
        return min+1;
    }

    /**
     * 层序遍历
     * 广度优先搜索从根节点开始，逐层访问所有节点。当首次遇到叶子节点时，就找到了最小深度。
     * @param treeNode
     * @return
     */
    public static int minDeepBFS(TreeNode<Integer> treeNode){
        Queue<TreeNode<Integer>> queue = new LinkedList<>();
        treeNode.deep=1;
        queue.offer(treeNode);
        while(!queue.isEmpty()){
            TreeNode<Integer> node = queue.poll();
            if(node.left == null && node.right == null){
                return node.deep;
            }
            if(node.left!=null){
                node.left.deep=node.deep+1;
                queue.offer(node.left);
            }
            if (node.right!=null){
                node.right.deep=node.deep+1;
                queue.offer(node.right);
            }
        }
        return 0;
    }
}
